package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56.合并区间
 *
 * @author cg
 * @program LeetCode->LeetCode_56
 * @create 2022-09-08 19:48
 **/
public class LeetCode_56 {

    @Test
    public void test56() {
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})));
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 4}, {4, 5}})));
    }

    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     * <p>
     * 示例 1：
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     * <p>
     * 示例2：
     * 输入：intervals = [[1,4],[4,5]]
     * 输出：[[1,5]]
     * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
     * <p>
     * 提示：
     * 1 <= intervals.length <= 10^4
     * intervals[i].length == 2
     * 0 <= start_i <= end_i <= 10^4
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 按照区间左边界从小到大排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        List<int[]> result = new ArrayList<>();
        // 初始为i-1的左边界
        int start = intervals[0][0];
        // 初始为i-1的右边界
        int rightMaxRound = intervals[0][1];
        // 合并区间，i从1开始
        for (int i = 1; i < intervals.length; i++) {
            // 当前下标的左边界大于上一个的右边界，说明他们没重叠，合并区间
            if (intervals[i][0] > rightMaxRound) {
                result.add(new int[]{start, rightMaxRound});
                // 左边界更新
                start = intervals[i][0];
            }
            // 右边界更新
            rightMaxRound = Math.max(rightMaxRound, intervals[i][1]);
        }
        // 合并最后一个区间
        result.add(new int[]{start, rightMaxRound});
        return result.toArray(new int[result.size()][]);
    }

}
